With the advent of tablet computers with handwritten pen input and with the advent of handwritten pen input for composing messages to be sent on the internet, there is an increasing need for a real time or on-line character recognizer.
In the past, a character recognizer has used a set of reference symbols and a procedure of estimating the similarity between input handwritten trajectory and the trajectory of a given reference symbol. The recognition answer is the reference symbol that has maximum similarity between its trajectory and the input trajectory.
In “Coding and comparison of DAGs (Directed Acyclic Graphs) as a novel neural structure with applications to on-line handwriting recognition,” by I-John Lin and S. Y. Kung (IEEE Transactions on Signal Processing, 45(11):2701-8, November, 1997, both the description of input trajectory and the description of the trajectory for each reference symbol are Directed Acyclic Graphs (DAGs). Having a certain similarity function defined on pairs (input graph edge, model graph edge), i.e. having a score assigning to any edge of a direct product of these two graphs, one can use a dynamic programming procedure for calculating similarity score of these graphs. Different paths connected between initial and last nodes in input graph and the initial and last nodes in the model graph can be interpreted as possible alternative descriptions of the input trajectory and the model trajectory, respectively. The main advantage of this approach is a possibility of choosing different descriptions of the same input trajectory segment while estimating its similarity to trajectory segments of different symbol models. This dynamic programming approach was described in the above-cited publication by I-John Lin and S. Y. Kung.